package com.zwj.interview.二分查找;

/**
 * 求一个非负整数的平方根
 */
public class 求平方根 {


    public int mySqrt(int n) {
        int left = 1;
        int right = n;
        while (left <= right) {
            //避免出现溢出的情况
            int mid = left + (right - left) / 2;
            if (mid <= n / mid) {
                /**
                 * 如果mid的平方≤n，那么接着判断（mid+1)的平方是否大于n。如果满足（m+1）的平方>n，那么m就是n的平方根
                 */
                if ((mid + 1) > n / (mid + 1)) {
                    return mid;
                }
                //走到这里，说明mid+1)2小于n，那么需要移动left
                left = mid + 1;
            } else {
                //到这里说明 mid的平方大于n,那么需要移动right
                right = mid - 1;
            }
        }
        //这是特殊情况，如果说函数输入一个0的话，那么left=1，right=0,不满足while判断，直接返回0
        return 0;
    }

}
